package cn.genmer.test.security.leetcode.medium;

import java.util.HashMap;
import java.util.Map;

/**
 3. 无重复字符的最长子串(大佬写法理解)
 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

我的题解: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/3-wu-zhong-fu-zi-fu-de-zui-chang-zi-chua-cm08/
 **/
public class NoRepeatLongestCharacters {

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring2("dvdf"));
        System.out.println(lengthOfLongestSubstring3("dvdf"));
    }

    /**
     * 硬写，失败
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        if(s.length() <= 0){
            return 0;
        }
        int flag = 1;
        int maxFlag =1;
        StringBuilder builder = new StringBuilder();
        char[] chars = s.toCharArray();
        builder.append(chars[0]);
        for(int i=1; i< s.length(); i++){
            if(builder.indexOf(String.valueOf(chars[i])) == -1){
                flag ++;
                    builder.append(chars[i]);
            } else{
                if(flag > maxFlag){
                    maxFlag = flag;
                }
                builder = new StringBuilder();
                if(flag == 1){
                    builder.append(chars[i]);
                } else{
                    // 例如 abcbea 这时是在e也就是下标4的位置上（从0开始），如果发现重复，应该回到b的位置重新往后查，所以的flag-1，最后的+1是弥补从0开始的差
                    builder.append(chars[i-(flag-1)]);
                }
                flag = 1;
            }
        }
        return flag > maxFlag? flag: maxFlag;
    }

    /**
     * Map实现
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring2(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>();
        for (int end = 0, start = 0; end < n; end++) {
            char alpha = s.charAt(end);
            if (map.containsKey(alpha)) {
                start = Math.max(map.get(alpha), start);
            }
            ans = Math.max(ans, end - start + 1);
            map.put(s.charAt(end), end + 1);
        }
        return ans;
    }

    /**
     * 数组实现
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring3(String s) {
        int[] m = new int[128];
        int len = 0;
        // 假设 测试用例为[d,v,d,f]
        // i为子字符串左边界指针（第一个字符下标），j为右边界指针（最后一个字符下标）
        // 再次确定下，i永远指向子字符串的开头位置，j永远指向子字符串结尾位置
        int i = 0;
        for(int j = 0; j < s.length(); j++){
            // 这里对m[s.charAt(j)]做一个详细分解，看得懂的直接跳过
            // s.charAt(j) 就是获取s字符串j位置的字符（按照刚开始跑的情况，j为0，取得的字符为：d）
            // m[s.charAt(j)] 我们知道，m是int型数组，Java中，char和int操作的时候， char会自动转成ascii码对应的值 d -> 100,v -> 118, f -> 102
            // 所以 m[s.charAt(j)] 在第一次，j=0的时候，s.charAt(j)是d的情况下，m[s.charAt(j)] -> m[100]

            // 1⃣ .这步的操作就是验证，j下标所在的字符是否已经存在过，如果存在过，就使用这个下标的值，为什么？ - 看 3⃣
            // 为什么没说max，因为下标肯定是增长的，这里默认就是使用最新的值
            i = Math.max(m[s.charAt(j)], i);

            // 2⃣ . ij为子字符串前后边界，相减可以得到长度，又因为下标从0开始，故+1
            len = Math.max(len, j - i + 1);
            // 3⃣ . 核心逻辑：如图1所示
            // 也就是说，在这个代码里， m[s.charAt(j)] = j + 1; 一开始无值，数组元素默认为0，在遇到比如说d，m[100]就有值了
            // 那这时候m[100]里放什么，就是放下一个字符串所在的位置，还是第一轮循环的情况，就是v的下标，覆盖的时候也是（比如第二次碰到d，m[100]的值就会存放f的下标），以此类推
            // 回答 1⃣ 的问题，应该覆盖了，左边界需要往后挪一个位置
            m[s.charAt(j)] = j + 1;


            // 最后最后（这个方法结果为3，子字符串为 vdf）
            // 然后就可以通过i所指向位置找到子字符串第一个字符 v, 通过数组m[v]也就是m[118]的值，找到值2，对应下标的值为d，通过d以此类推获得f的下标
            // 就可以获取子字符串
        }
        return len;
    }
}
